package khiem.java.sample.genericgrapth;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

import org.apache.logging.log4j.LogManager;
import org.apache.logging.log4j.Logger;

import sun.nio.cs.ext.PCK;

import com.automic.pm.core.PackageDependency;
import com.automic.pm.core.PackageInfo;
import com.automic.pm.core.PackageRepository;
import com.automic.pm.versioning.Version;
import com.google.common.base.Predicate;
import com.google.common.collect.Sets;

public class DependencyResolver {

    private PackageRepository<PackageInfo> graph;
    
    private Logger logger = LogManager.getLogger(this.getClass());
        
    public DependencyResolver(PackageRepository<PackageInfo> graph) {
        this.graph = graph;
    }

    /**
     * Node is resolved if ALL of its dependencies are resolvable.<br> 
     * Node is invalid if ONE of its dependencies is unresolvable.<br>
     * Node is valid if it's still in progress of determining it's validity.<br> 
     * Node is unresolved if it's still in progress of resolving.<br>
     */
    private Set<PackageInfo> resolved = new LinkedHashSet<PackageInfo>();
    private Set<PackageInfo> unresolved = new LinkedHashSet<PackageInfo>();
    private Set<PackageInfo> valid = new LinkedHashSet<PackageInfo>();
    private Set<PackageInfo> invalid = new HashSet<PackageInfo>();
    
    public Set<List<PackageInfo>> circulars = new HashSet<>();
    
    private Map<PackageInfo, List<PackageInfo>> depGroups = new HashMap<>();
    
    private Map<String, List<String>> dependantMap;

    /**
     * Starts resolve recursively from the given node
     * @param start
     * @param level
     */
    public void tryResolving(PackageInfo start, int level) {
        valid.add(start);
        if (graph.getInstalledNodes().contains(start)) {
            resolved.add(start);
            return;
        }
        unresolved.add(start);

        for (PackageDependency dp : start.getPackageDependencies()) {
            // with given node name, get list of target node
            String targetNodeName = dp.getPackageName();
            Map<String, PackageInfo> nodeVersions = graph.getNodeMap().get(targetNodeName);
            
            // if there's an installed version, removing all out-dated versions and add installed one to nodeVersions list
            if (graph.isInstalled(targetNodeName)) {
                PackageInfo installed = graph.getInstalledNode(targetNodeName);
                if (nodeVersions == null) nodeVersions = new HashMap<>();
                Iterator<Entry<String, PackageInfo>> iter =  nodeVersions.entrySet().iterator();
                while (iter.hasNext()) {
                    Entry<String, PackageInfo> entry = iter.next();
                    if (entry.getValue().getVersion().compareTo(installed.getVersion()) < 0) {
                        logger.debug("Package {} is eliminated as the newer version {} installed", entry.getValue(), installed);
                        iter.remove();
                    }
                }
                
                // add installed version to list of versions to evaluate
                nodeVersions.put(installed.getVersion().toString(), installed);
            }

            // no node with target name available from graph
            if (nodeVersions == null || nodeVersions.size() == 0) {
                logger.debug("Dependency from {} to {} couldn't be resolved: there's no version of {} available", start, dp, targetNodeName);
                logger.debug("{} is invalid", start);
                invalid.add(start);
                valid.remove(start);
                break;
            }

            // check if there's a target node version satisfies the condition
            List<PackageInfo> satisfied = new ArrayList<PackageInfo>();
            for (String version : nodeVersions.keySet()) {
                PackageInfo node = nodeVersions.get(version);
                if (invalid.contains(node)) continue; // skip if this node is invalid

                // validate node with dependency condition
                if (dp.validate(node)) {
                    satisfied.add(node);
                }
            }

            // if no target node version satisfies, the start node will be marked as invalid
            // and the dependency is marked as unresolved
            if (satisfied.size() == 0) {
                invalid.add(start);
                valid.remove(start);
                logger.debug("Dependency from {} to {} couldn't be resolved: no satisfied package found", start, dp);
                logger.debug("{} is invalid", start);
                break;
            }

            List<PackageInfo> circular = new ArrayList<PackageInfo>();
            // try resolve each target node version
            for (PackageInfo node : satisfied) {
                // if the node is in 'unresolved' list, this is a circular dependency?
                if (unresolved.contains(node)) {
                    logger.debug("Circular dependency detected {} -> {}, with {}", start, dp, node);
                    circular.add(node);
                    
                    // 
                    List<PackageInfo> circle = new ArrayList<>();
                    boolean found = false;
                    for (PackageInfo pkg : unresolved) {
                        if (found) circle.add(pkg);
                        else {
                            if (!pkg.equals(node)) continue;
                            else {
                                found = true;
                                circle.add(pkg);
                            }
                        }
                    }
                    circulars.add(circle);
                    
                    continue;
                }
                tryResolving(node, level + 1);
            }

            // filter out invalid or circular nodes
            Iterator<PackageInfo> iter = satisfied.iterator();
            while (iter.hasNext()) {
                PackageInfo node = iter.next();
                if (invalid.contains(node) || circular.contains(node)) {
                    iter.remove();
                }
            }

            // the dependency is resolved only if one of satisfied node is resolved
            if (satisfied.size() > 0) {
                logger.debug("Resolved dependency {} -> {}: {}", start, dp, satisfied);
                if (!depGroups.containsKey(start)) depGroups.put(start, satisfied);
                else depGroups.get(start).addAll(satisfied);
                if (level == 0) logger.debug("");
            } else {
                invalid.add(start);
                valid.remove(start);
                logger.debug("Dependency from {} to {} couldn't be resolved", start, dp);
                logger.debug("{} is invalid", start);
                break;
            }
        }
        unresolved.remove(start);
        // node is resolved if it's not invalid after checking all dependencies
        if (!invalid.contains(start)) resolved.add(start);
    }
    
    public boolean findIntersections(List<Set<PackageInfo>> intersections) {
        logger.debug("Valid nodes:");
        for (PackageInfo node : valid) {
            logger.debug(node.getName() + ", " + node.getVersion());
        }

        // depNodes the set of node names from dependency groups
        Set<String> depNodes = new HashSet<>();
        logger.debug("Dependencies Groups:");
        for (PackageInfo node : depGroups.keySet()) {
            logger.debug("{}: {}", node, depGroups.get(node));

            for (PackageInfo dNode : depGroups.get(node)) {
                depNodes.add(dNode.getName());
            }
        }

        boolean resolvable = true;
        logger.debug("Calculate package version intersections:");

        // for each node name appears more than once, from dependency groups that contains that
        // name, extract the intersection
        for (final String nodeName : depNodes) {
            // list of sets containing this nodeName
            List<Set<PackageInfo>> dgSets = new ArrayList<>();
            // from the depGroups, find all groups contain this nodeName
            for (List<PackageInfo> dg : depGroups.values()) {
                Set<PackageInfo> dgSet = Sets.filter(Sets.newHashSet(dg), new Predicate<PackageInfo>() {
                    @Override
                    public boolean apply(PackageInfo arg0) {
                        return arg0.getName().equals(nodeName);
                    }
                });

                if (dgSet.size() > 0) {
                    dgSets.add(dgSet);
                }
            }

            // find intersection of sets in the dgSets obj
            Set<PackageInfo> firstSet = dgSets.get(0);
            Set<PackageInfo> intersection = null;
            if (dgSets.size() == 1) intersection = Sets.intersection(firstSet, firstSet); 
            else {
                for (int i = 1; i < dgSets.size(); i++) {
                    intersection = Sets.intersection(firstSet, dgSets.get(i));
                }
            }
            if (intersection == null || intersection.size() < 1) {
                logger.debug("Couldn't resolve version of package {}", nodeName);
                resolvable = false;
                break;
            } else {
                intersection = Sets.newHashSet(intersection); // by this way intersection is modifiable
                intersections.add(intersection);
                logger.debug(intersection);
            }
        }

        if (!resolvable) {
            logger.info("Dependency resolution finished with failure!");
            return false;
        }
        
        return true;
    }

    /**
     * Finds dependency resolution from valid nodes and dependency groups
     */
    public boolean chooseBestVersions(List<Set<PackageInfo>> intersections) {     
        Set<String> depNodes = new HashSet<>();
        for (Set<PackageInfo> intersection : intersections) {
            for (PackageInfo node : intersection) {
                depNodes.add(node.getName());
            }
        }
        
        // try to remove all packages version that can cause conflict with installed packages in AE
        for (Set<PackageInfo> intersection : intersections) {
            String nodeName = intersection.iterator().next().getName();
            if (graph.isInstalled(nodeName)) {
                Set<PackageInfo> conflicts = Sets.newHashSet();
                Version installedV = graph.getInstalledVersion(nodeName);
                for (PackageInfo node : intersection) {
                    if (node.getVersion().compareTo(installedV) > 0) {
                        // check conflict, a node causes conflict if it breaks dependencies of other node that is not in update list
                        // first, get list of installed node that would be broken by this node
                        // then check if one of those node are not in update list
                        List<PackageInfo> brokens = graph.getBrokenNodesBy(node);
                        for (PackageInfo broken : brokens) {
                          String bNodeName = broken.getName();
                          if (!depNodes.contains(bNodeName)) {
                            logger.debug("{} is eliminated as it causes conflict with {}", node, broken);
                            conflicts.add(node);
                            break;
                          }
                        }                    
                    }
                }

                intersection.removeAll(conflicts);
                if (intersection.size() == 0) {
                    logger.debug("Couldn't resolve version of package {}. Conflict discovered in all possible versions.", nodeName);
                    return false;
                }
            }
        }
        
        // from intersections, choosing the best version for each intersection set
        logger.debug("Choosing best match package versions:");
        for (Set<PackageInfo> intersection : intersections) {
            PackageInfo best = null;
            if (intersection.size() > 1) {
                List<PackageInfo> interList = new ArrayList<>(intersection);
                Collections.sort(interList);
                // choose only the mininum
                best = interList.get(0);
            } else best = intersection.iterator().next();

            logger.debug(best);

            final String bestName = best.getName();
            final String bestVersion = best.getVersion().toString();
            // filter out all nodes that is not 'best' from valid list
            // that's how we get the final list of valid nodes
            valid = Sets.filter(valid, new Predicate<PackageInfo>() {
                @Override
                public boolean apply(PackageInfo arg0) {
                    return (!arg0.getName().equals(bestName) || bestVersion.equals(arg0.getVersion().toString()));
                }
            });
        }

        logger.debug("Valid nodes:");
        for (PackageInfo node : valid) {
            logger.debug(node);
        }

        // sync. resolved list with valid list
        resolved = Sets.intersection(resolved, valid);

        logger.info("Resolve order:");
        for (PackageInfo node : resolved) {
            logger.info(node);
        }
        
        return true;
    }

    /**
     * Resets resolver
     */
    private void reset() {
        resolved = new LinkedHashSet<PackageInfo>();
        unresolved = new HashSet<PackageInfo>();
        valid = new LinkedHashSet<PackageInfo>();
        invalid = new HashSet<PackageInfo>();
        depGroups = new HashMap<>();
    }
    
    /**
     * Build dependant map, each map entry is a pair of package name and its list of dependant packages name
     */
    private void buildDependantMap() {
        dependantMap = new HashMap<>();
        for (PackageInfo pkg : graph.getInstalledNodes()) {
            List<PackageDependency> deps = pkg.getPackageDependencies();
            for (PackageDependency dep : deps) {
                String depName = dep.getPackageName();
                if (!dependantMap.containsKey(depName)) {
                    dependantMap.put(depName, new ArrayList<String>());
                }
                if (!dependantMap.get(depName).contains(pkg.getName())) dependantMap.get(depName).add(pkg.getName());
            }
        }
    }
    
    /**
     * Recursively resolves uninstalling from given node
     * @param node node to uninstall
     * @return true if node is recursively un-installable, otherwise false
     */
    private boolean tryUninstResolving(PackageInfo node) {      
        if (!dependantMap.containsKey(node.getName())) {
            // no node could be affected by uninstalling this node
            resolved.add(node);
            return true;
        }
        unresolved.add(node);
        for (String dependant : dependantMap.get(node.getName())) {
            PackageInfo dependantNode = graph.getInstalledNode(dependant);
            if (!resolved.contains(dependantNode)) {
                if (unresolved.contains(dependantNode)) {
                    // circular dependency
                    logger.debug("Circular dependency found between {} and {}", dependantNode, node);
                    logger.debug("Couldn't resolve {} for uninstalling", node);
                    unresolved.remove(node);
                    return false;
                }
                if (!tryUninstResolving(dependantNode)) {
                    logger.debug("Couldn't resolve {} for uninstalling", node);
                    unresolved.remove(node);
                    return false;
                }
            }
        }
        unresolved.remove(node);
        resolved.add(node); 
        return true;
    }

    /**
     * Resolves installing recursively
     * @param node package to install recursively
     * @return
     */
    public boolean resolve(PackageInfo node) {
        reset();
        logger.info("Try resolving dependencies for {}", node);
        tryResolving(node, 0);
        if (!valid.contains(node)) return false;
        List<Set<PackageInfo>> intersections = new ArrayList<Set<PackageInfo>>();
        if (findIntersections(intersections)) {
            return chooseBestVersions(intersections);
        } else return false;
    }
    
    /**
     * Resolves uninstalling recursively
     * @param node package to uninstall recursively
     * @return
     */
    public boolean uninstResolve(PackageInfo node) {
        reset();
        buildDependantMap();
        tryUninstResolving(node);
        return resolved.contains(node);
    }

    /**
     * Gets resolved resolution in right order
     * @return <code>Set</code> of <code>PackageInfo</code> objects in apropriate order
     */
    public Set<PackageInfo> getResolved() {
        return resolved;
    }

    public Set<PackageInfo> getValid() {
        return valid;
    }

    public Set<PackageInfo> getInvalid() {
        return invalid;
    }

    public Map<PackageInfo, List<PackageInfo>> getDepGroups() {
        return depGroups;
    }
}
